package com.lfg.leetcode.leetcode200;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class No241diffWaysToCompute {

    public static void main(String[] args) {
        List<Integer> ret = diffWaysToCompute("2*3-4*5");
        for (int i : ret) {
            System.out.println(i);
        }
    }

    public static List<Integer> diffWaysToCompute(String input) {
        if (null == input || input.length() == 0) {
            return new ArrayList<>();
        }
        int length = input.length();
        return diffWaysToCompute(input, new HashMap<String, List<Integer>>(length * length));
    }

    public static List<Integer> diffWaysToCompute(String input, Map<String, List<Integer>> hm) {
        if (hm.containsKey(input)) {
            return hm.get(input);
        }
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < input.length(); i++) {
            char ch = input.charAt(i);
            if (ch == '+' || ch == '-' || ch == '*') {
                for (Integer l : diffWaysToCompute(input.substring(0, i))) {
                    for (Integer r : diffWaysToCompute(input.substring(i + 1, input.length()))) {
                        if (ch == '+') {
                            res.add(l + r);
                        } else if (ch == '-') {
                            res.add(l - r);
                        } else {
                            res.add(l * r);
                        }
                    }
                }
            }
        }
        if (res.size() == 0) {
            res.add(Integer.valueOf(input));
        }
        hm.put(input, res);
        return res;
    }


}
